
import java.util.ArrayList;
import java.util.BitSet;  
import java.util.HashMap;  
  
  
public class Geohash {  
  
    private static int numbits = 6 * 5;  
    final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',  
            '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',  
            'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };  
      
    final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();  
    final static HashMap<Integer, Character> uplook = new HashMap<Integer, Character>(); 
    static {  //只加载一次
        int i = 0;  
        for (char c : digits)  
            lookup.put(c, i++); 
    }  
    static{
    	for(int i=0;i<digits.length;i++){
    		uplook.put(i, digits[i]);
    	}
    }
  
    public static void main(String[] args)  throws Exception{  
        System.out.println(new Geohash().encode(-84.50104,-169.10043));  
        System.out.println(new Geohash().encode(84.50104,169.10043));
//        System.out.println(new Geohash().encodeMaxlevel(39.25174573651331,122.80512079654339,35));  
        double[] shuzu=new Geohash().decode("zz210cf2kq");
        System.out.println(shuzu[0]);
        System.out.println(shuzu[1]);     
        double [] shuzu1=new Geohash().bitdecode("1");
        System.out.print(shuzu1[0]);
        System.out.print(" ");
        System.out.println(shuzu1[1]);
        System.out.print(shuzu1[2]);
        System.out.print(" ");
        System.out.println(shuzu1[3]);
//        String polygonstring="POLYGON(("+String.valueOf(shuzu1[0])+" "+String.valueOf(shuzu1[2])+","+" "+String.valueOf(shuzu1[0])+" "+String.valueOf(shuzu1[3])+","+" "+String.valueOf(shuzu1[1])+" "+String.valueOf(shuzu1[2])+","+" "+String.valueOf(shuzu1[1])+" "+String.valueOf(shuzu1[3])+"))";
//        System.out.println(polygonstring);
        ArrayList<String> result=new ArrayList<String>();
        result=new Geohash().resultArray("11");
        for(int i=0;i<result.size();i++){
        	System.out.println(result.get(i));
        }
    }  
/*把一维geohash码转化成二维数组*/
    public double[] decode(String geohash) {  
        StringBuilder buffer = new StringBuilder();  
        for (char c : geohash.toCharArray()) {
            int i = lookup.get(c) + 32;  
            buffer.append(Integer.toString(i,2).substring(1));
        }  
       
        BitSet lonset = new BitSet();  
        BitSet latset = new BitSet();  
        int lonlength=0;
        int latlength=0;
        if(buffer.length()%2==0){
        	   lonlength=buffer.length()/2;
        	   latlength=buffer.length()/2;
        }
        else{
        	   lonlength=buffer.length()/2+1;
        	   latlength=buffer.length()/2;
        } 
        //even bits偶数位经度  
        int j =0;  
        for (int i=0; i< buffer.length();i+=2) {  
            boolean isSet = false;  
            if ( i < buffer.length() ){
            	  isSet = buffer.charAt(i) == '1';
            }    
            lonset.set(j++, isSet);
        } 
        //odd bits 奇数放纬度 
        j=0;  
        for (int i=1; i< buffer.length();i+=2) {  
            boolean isSet = false;  
            if ( i < buffer.length() )  
              isSet = buffer.charAt(i) == '1';  
            latset.set(j++, isSet);  
        }
        StringBuilder lonbuffer=new StringBuilder();
        for (int i = 0; i <lonlength; i++) {  //偶数位放精度，基数位放维度
            lonbuffer.append( (lonset.get(i))?'1':'0');  
        } 
       StringBuilder latbuffer=new StringBuilder();
       for(int i=0;i<latlength;i++){
    	   latbuffer.append( (latset.get(i))?'1':'0');
       }
        double lon = decode(lonbuffer, -180, 180);  
        double lat = decode(latbuffer, -90, 90);  
          
        return new double[] {lat, lon};       
    }  
    public double[] bitdecode(String geohash){  
        StringBuilder buffer = new StringBuilder();
        buffer.append(geohash);  
        int lonlength=0;
        int latlength=0;
        if(buffer.length()%2==0){
        	   lonlength=buffer.length()/2;
        	   latlength=buffer.length()/2;
        }
        else{
        	   lonlength=buffer.length()/2+1;
        	   latlength=buffer.length()/2;
        }
        
        BitSet lonset = new BitSet(lonlength);  
        BitSet latset = new BitSet(latlength);  
        
        //even bits偶数位经度  
        int j =0;  
        for (int i=0; i< buffer.length();i+=2) {  
            boolean isSet = false;  
            if ( buffer.charAt(i)=='1')  
                isSet = true;
            else
            	    isSet= false;
            lonset.set(j,isSet);
            j++;
        } 
        //odd bits 奇数放纬度 
        j=0;  
        for (int i=1; i< buffer.length();i+=2) {  
            boolean isSet = false;  
            if ( buffer.charAt(i)=='1')  
                isSet = true;
            else
            	    isSet= false;
            latset.set(j,isSet);  
            j++;
        }  
        StringBuilder lonbuffer=new StringBuilder();
        for (int i = 0; i <lonlength; i++) {  //偶数位放精度，基数位放维度
            lonbuffer.append( (lonset.get(i))?'1':'0');  
        } 
       StringBuilder latbuffer=new StringBuilder();
       for(int i=0;i<latlength;i++){
    	   latbuffer.append( (latset.get(i))?'1':'0');
       }
       double []shuzu1=bitdecode(lonbuffer, -180, 180);
       double []shuzu2=bitdecode(latbuffer, -90, 90);
	return new double[] {shuzu1[0],shuzu1[1],shuzu2[0],shuzu2[1]};
    }
    private double[] bitdecode(StringBuilder bs, double floor, double ceiling) {
		double mid=0;
		double key = 0;
	    if(bs.length()==0){
	    	return new double[] {floor,ceiling};
	    }
	    else{
	    	for(int i=0;i<bs.length();i++){
				mid=(floor + ceiling) / 2;
	            if (bs.charAt(i)=='1'){
	                floor = mid;
	                key=ceiling;
	            }
	            else{
	                ceiling = mid; 
	                key=floor;
	            }
			}
			if(mid>key){
				return new double[] {key,mid}; 
			}
			else {
				return new double[] {mid,key};
			}
	    }		
	}
    private double decode(StringBuilder bs, double floor, double ceiling) {  
        double mid = 0;  
        for (int i=0; i<bs.length(); i++) {  
            mid = (floor + ceiling) / 2;  
            if (bs.charAt(i)=='1')
                floor = mid;
            else  
                ceiling = mid;  
        }  
        return mid;  
    }
    /*将二进制字符串型的geohash值转化成一组Base32编码的geohash值*/
	public ArrayList<String> resultArray(String geohash){
    	int length=geohash.length();
    	int minlevel=length/5;
    	int yushu=length%5;
    	int change=5-yushu;
    	String string="";
    	ArrayList<String> result=new ArrayList<String>();
    	if(minlevel>0){
    		for(int i=0;i<minlevel;i++){
    			String goal=geohash.substring(i*5, i*5+5);
    			int key=Integer.valueOf(goal, 2);
    			string=string+uplook.get(key);
    		}
    	}
//    	System.out.println(string);
    	if(yushu!=0){
    		String goal=geohash.substring(minlevel*5,minlevel*5+yushu);
//    		System.out.println(goal);
    		String changezero="";
    		for(int i=0;i<change;i++){
    			changezero=changezero+"0";
    		}
    		int key=Integer.valueOf(goal+changezero,2);
//    		System.out.println(key);
    		int jiashu=(int) Math.pow(2, change);
    		int [] countkey=new int[jiashu];
    		for(int i=0;i<jiashu;i++){
    			countkey[i]=i+key;
    		}
    		for(int i=0;i<jiashu;i++){
    			result.add(string+uplook.get(countkey[i]).toString());
    		}
    	}
		else {
			result.add(string);
		}
    	return result;
    }
      
/*把二维数组转化成一维geohash码*/ 
    //先放纬度再放经度    
    public String encode(double lat, double lon) {  
        BitSet latbits = getBits(lat, -90, 90);
        BitSet lonbits = getBits(lon, -180, 180);  
        StringBuilder buffer = new StringBuilder();  
        for (int i = 0; i < numbits; i++) {  //偶数位放精度，基数位放维度
            buffer.append( (lonbits.get(i))?'1':'0');  
            buffer.append( (latbits.get(i))?'1':'0');  
        } 
//        System.out.println(Long.parseLong(buffer.toString()+"0000",2));
//        System.out.println(buffer.toString());
//        System.out.println(base32(buffer.toString()));
//        System.out.println(base32(Long.parseLong(buffer.toString(),2)));
        return base32(buffer.toString());  
//        return buffer.toString();
    } 
    public String encodeMaxlevel(double lat, double lon,int maxlevel){
    	BitSet latbits = getBits(lat, -90, 90);
        BitSet lonbits = getBits(lon, -180, 180);  
        StringBuilder buffer = new StringBuilder();  
        for (int i = 0; i < numbits; i++) {  //偶数位放精度，基数位放维度
            buffer.append( (lonbits.get(i))?'1':'0');  
            buffer.append( (latbits.get(i))?'1':'0');  
        } 
        return buffer.toString().substring(0,maxlevel);
    }
  
    private BitSet getBits(double lat, double floor, double ceiling) {  
        BitSet buffer = new BitSet(numbits);  
        for (int i = 0; i < numbits; i++) {  
            double mid = (floor + ceiling) / 2;  
            if (lat >= mid) {  
                buffer.set(i);  
                floor = mid;  
            } else {  
                ceiling = mid;  
            }  
        } 
        return buffer;  
    }  
    public static String base32(String string){
    	    String key="";
    	    int count=0;
    	    String reslut="";
    	    for(int i=0;i<string.length();i++){
    	    	  count++;
    	    	  if(count<5){
    	    		  key=key+string.charAt(i);   	    		 
    	    	  }
    	    	  else if(count==5){   	    		  
    	    		  key=key+string.charAt(i);
    	    		  count=0;
    	    		  int shijinzhi=Integer.parseInt(key,2);
    	    		  reslut=reslut+uplook.get(shijinzhi);
    	    		  key="";
    	    	  }
    	    }
		return reslut;   	
    }
    public static String base32(long i) {  
        char[] buf = new char[65];  
        int charPos = 64;  
        boolean negative = (i < 0);  
        if (!negative)  
            i = -i;  
        while (i <= -32) {  
            buf[charPos--] = digits[(int) (-(i % 32))];  
            i /= 32;  
        }  
        buf[charPos] = digits[(int) (-i)];  
  
        if (negative)  
            buf[--charPos] = '-';  
        return new String(buf, charPos, (65 - charPos));  
    }  
  
}